package club.xiaojiawei.binarytree;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/17/22 12:53 AM
 * @question 654. 最大二叉树
 * @description 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 * 创建一个根节点，其值为 nums 中的最大值。
 * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * 返回 nums 构建的 最大二叉树
 */
public class ConstructMaximumBinaryTree654 {

    public static void main(String[] args) {
        ConstructMaximumBinaryTree654 test = new ConstructMaximumBinaryTree654();
        TreeNode result = test.constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
        System.out.println(result);
    }

    /**
     * 递归
     * @param nums
     * @return
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return recursion(nums, 0, nums.length - 1);
    }

    public TreeNode recursion(int[] nums, int left, int right){
        if (left > right){
            return null;
        }
        int max = -1;
        int index = -1;
        for (int i = left; i <= right; i++){
            if (nums[i] > max){
                max = nums[i];
                index = i;
            }
        }
        TreeNode node = new TreeNode(max);
        node.left = recursion(nums, left, index - 1);
        node.right = recursion(nums, index + 1, right);
        return node;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
